public class Solution {
    public int minDistance(int[] houses, int k) {
        Arrays.sort(houses);
        int n = houses.length;
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                dp[i][j] += Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i][1] += Math.abs(houses[j] - houses[i / 2]);
            }
        }
        for (int j = 1; j < k; j++) {
            for (int i = j; i < n; i++) {
                for (int x = 1; x <= i + 1 - j; x++) {
                    int y = 0;
                    for (int p = i + 1 - x; p < i + 1; p++) {
                        y += Math.abs(houses[p] - houses[(2 * i - x + 1) / 2]);
                    }
                    dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i + 1 - x][j] + y);
                }
            }
        }
        return dp[n][k];
    }
}